Search Results

Documents authored by Ellen, Faith

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.6
The Step Complexity of Multidimensional Approximate Agreement

Authors: Hagit Attiya and Faith Ellen

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Approximate agreement allows a set of n processes to obtain outputs that are within a specified distance ε > 0 of one another and within the convex hull of the inputs. When the inputs are real numbers, there is a wait-free shared-memory approximate agreement algorithm [Moran, 1995] whose step complexity is in O(n log(S/ε)), where S, the spread of the inputs, is the maximal distance between inputs. There is another wait-free algorithm [Schenk, 1995] that avoids the dependence on n and achieves O(log(M/ε)) step complexity where M, the magnitude of the inputs, is the absolute value of the maximal input. This paper considers whether it is possible to obtain an approximate agreement algorithm whose step complexity depends on neither n nor the magnitude of the inputs, which can be much larger than their spread. On the negative side, we prove that Ω(min{(log M)/(log log M), (√log n)/(log log n)}) is a lower bound on the step complexity of approximate agreement, even when the inputs are real numbers. On the positive side, we prove that a polylogarithmic dependence on n and S/ε can be achieved, by presenting an approximate agreement algorithm with O(log n (log n + log(S/ε))) step complexity. Our algorithm works for multidimensional domains. The step complexity can be further restricted to be in O(min{log n (log n + log (S/ε)), log(M/ε)}) when the inputs are real numbers.
Cite as

Hagit Attiya and Faith Ellen. The Step Complexity of Multidimensional Approximate Agreement. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2022.6,
  author =	{Attiya, Hagit and Ellen, Faith},
  title =	{{The Step Complexity of Multidimensional Approximate Agreement}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.6},
  URN =		{urn:nbn:de:0030-drops-176261},
  doi =		{10.4230/LIPIcs.OPODIS.2022.6},
  annote =	{Keywords: approximate agreement, conflict detection, shared memory, wait-freedom, step complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.36
Extension-Based Proofs for Synchronous Message Passing

Authors: Yilun Sheng and Faith Ellen

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
There is no wait-free algorithm that solves k-set agreement among n ≥ k+1 processes in asynchronous systems where processes communicate using only registers. However, proofs of this result for k ≥ 2 are complicated and involve topological reasoning. To explain why such sophisticated arguments are necessary, Alistarh, Aspnes, Ellen, Gelashvili, and Zhu recently introduced extension-based proofs, which generalize valency arguments, and proved that there are no extension-based proofs of this result. In the synchronous message passing model, k-set agreement is solvable, but there is a lower bound of t rounds for any k-set agreement algorithm among n > kt processes when at most k processes can crash each round. The proof of this result for k ≥ 2 is also a complicated topological argument. We define a notion of extension-based proofs for this model and we show there are no extension-based proofs that t rounds are necessary for any k-set agreement algorithm among n = kt+1 processes, for k ≥ 2 and t > 2, when at most k processes can crash each round. In particular, our result shows that no valency argument can prove this lower bound.
Cite as

Yilun Sheng and Faith Ellen. Extension-Based Proofs for Synchronous Message Passing. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sheng_et_al:LIPIcs.DISC.2021.36,
  author =	{Sheng, Yilun and Ellen, Faith},
  title =	{{Extension-Based Proofs for Synchronous Message Passing}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.36},
  URN =		{urn:nbn:de:0030-drops-148380},
  doi =		{10.4230/LIPIcs.DISC.2021.36},
  annote =	{Keywords: Set agreement, lower bounds, valency arguments}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.26
Space Lower Bounds for the Signal Detection Problem

Authors: Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Many shared memory algorithms have to deal with the problem of determining whether the value of a shared object has changed in between two successive accesses of that object by a process when the responses from both are the same. Motivated by this problem, we define the signal detection problem, which can be studied on a purely combinatorial level. Consider a system with n+1 processes consisting of n readers and one signaller. The processes communicate through a shared blackboard that can store a value from a domain of size m. Processes are scheduled by an adversary. When scheduled, a process reads the blackboard, modifies its contents arbitrarily, and, provided it is a reader, returns a Boolean value. A reader must return true if the signaller has taken a step since the reader’s preceding step; otherwise it must return false. Intuitively, in a system with n processes, signal detection should require at least n bits of shared information, i.e., m >= 2^n. But a proof of this conjecture remains elusive. We prove a lower bound of m >= n^2, as well as a tight lower bound of m >= 2^n for two restricted versions of the problem, where the processes are oblivious or where the signaller always resets the blackboard to the same fixed value. We also consider a one-shot version of the problem, where each reader takes at most two steps. In this case, we prove that it is necessary and sufficient that the blackboard can store m=n+1 values.
Cite as

Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu. Space Lower Bounds for the Signal Detection Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ellen_et_al:LIPIcs.STACS.2019.26,
  author =	{Ellen, Faith and Gelashvili, Rati and Woelfel, Philipp and Zhu, Leqi},
  title =	{{Space Lower Bounds for the Signal Detection Problem}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.26},
  URN =		{urn:nbn:de:0030-drops-102654},
  doi =		{10.4230/LIPIcs.STACS.2019.26},
  annote =	{Keywords: Signal detection, ABA problem, space complexity, lower bound}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2018
LIPIcs, Volume 125, OPODIS'18, Complete Volume

Authors: Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
LIPIcs, Volume 125, OPODIS'18, Complete Volume
Cite as

22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{cao_et_al:LIPIcs.OPODIS.2018,
  title =	{{LIPIcs, Volume 125, OPODIS'18, Complete Volume}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018},
  URN =		{urn:nbn:de:0030-drops-101742},
  doi =		{10.4230/LIPIcs.OPODIS.2018},
  annote =	{Keywords: Computer systems organization, Dependable and fault-tolerant systems and networks, Computing methodologies, Distributed algorithms, Networks, Mobile networks, Wireless access networks, Ad hoc networks, Software and its engineering, Distributed systems organizing principles,}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo Ferreira

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.OPODIS.2018.0,
  author =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.0},
  URN =		{urn:nbn:de:0030-drops-100607},
  doi =		{10.4230/LIPIcs.OPODIS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2016.4
Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract)

Authors: Faith Ellen

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The participating set problem can be solved in an asynchronous system using only registers. I will gently explain this problem and its solution, followed by a new extension, called consistent ordered partition. Next, I will present a wait-free simulation by f + 1 processes of any setconsensus algorithm that tolerates f faults. I will also describe how to extend this simulation using consistent ordered partition. Finally, I will discuss how this extension can be used to prove that, within every level m > 1 of the consensus hierarchy, there is an infinite sequence of increasingly more powerful deterministic objects.
Cite as

Faith Ellen. Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract). In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ellen:LIPIcs.OPODIS.2016.4,
  author =	{Ellen, Faith},
  title =	{{Participating Sets, Simulations, and the Consensus Hierarchy}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.4},
  URN =		{urn:nbn:de:0030-drops-70736},
  doi =		{10.4230/LIPIcs.OPODIS.2016.4},
  annote =	{Keywords: Consensus, shared-memory systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.17
Atomic Snapshots from Small Registers

Authors: Leqi Zhu and Faith Ellen

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Existing n-process implementations of atomic snapshots from registers use large registers. We consider the problem of implementing an m-component snapshot from small, Theta(log(n))-bit registers. A natural solution is to consider simulating the large registers. Doing so straightforwardly can significantly increase the step complexity. We introduce the notion of an interruptible read and show how it can reduce the step complexity of simulating the large registers in the snapshot of Afek et al. In particular, we show how to modify a recent large register simulation to support interruptible reads. Using this modified simulation, the step complexity of UPDATE and SCAN changes from Theta(n*m) to Theta(n*m+m*w), instead of Theta(n*m*w), if each component of the snapshot consists of Theta(w*log(n)) bits. We also show how to modify a limited-use snapshot to use small registers when the number of UPDATE operations is in n^{O(1)}. In this case, we change the step complexity of UPDATE from Theta((log(n))^3) to O(w + (log(n))^2*log(m)) and the step complexity of SCAN from Theta(log(n)) to O(m*w + log(n)).
Cite as

Leqi Zhu and Faith Ellen. Atomic Snapshots from Small Registers. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{zhu_et_al:LIPIcs.OPODIS.2015.17,
  author =	{Zhu, Leqi and Ellen, Faith},
  title =	{{Atomic Snapshots from Small Registers}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.17},
  URN =		{urn:nbn:de:0030-drops-66084},
  doi =		{10.4230/LIPIcs.OPODIS.2015.17},
  annote =	{Keywords: atomic snapshot, limited-use snapshot, small registers, simulation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact